/*
Leetcode 407
给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
    int trapRainWater(vector<vector<int>> &heightMap)
    {
        const int M = heightMap.size();
        if (M < 3)
            return 0;
        const int N = heightMap[0].size();
        if (N < 3)
            return 0;
        vector<vector<int>> water_limit(1, vector<int>(N, 0));
        water_limit.push_back(vector<int>(N, INT32_MAX));
        water_limit[1][0] = 0;
        water_limit[1][N - 1] = 0;
        for (int i = 2; i < M - 1; i++)
        {
            water_limit.push_back(water_limit[1]);
        }
        water_limit.push_back(water_limit[0]);

        bool overflow = true;
        while (overflow)
        {
            overflow = false;
            for (int i = 1; i < M - 1; i++)
            {
                for (int j = 1; j < N - 1; j++)
                {
                    const int height = min(max(water_limit[i - 1][j], heightMap[i - 1][j]), max(water_limit[i][j - 1], heightMap[i][j - 1]));
                    if (water_limit[i][j] > height)
                    {
                        if (!overflow)
                            overflow = true;
                        water_limit[i][j] = height;
                    }
                }
            }
            if (!overflow)
                break;

            overflow = false;
            for (int i = M - 2; i > 0; i--)
            {
                for (int j = N - 2; j > 0; j--)
                {
                    const int height = min(max(water_limit[i + 1][j], heightMap[i + 1][j]), max(water_limit[i][j + 1], heightMap[i][j + 1]));
                    if (water_limit[i][j] > height)
                    {
                        if (!overflow)
                            overflow = true;
                        water_limit[i][j] = height;
                    }
                }
            }
        }
        int volumn = 0;
        for (int i = 1; i < M - 1; i++)
        {
            for (int j = 1; j < N - 1; j++)
            {
                if (water_limit[i][j] <= heightMap[i][j])
                    continue;
                volumn += water_limit[i][j] - heightMap[i][j];
            }
        }
        return volumn;
    }
};